package com.hyper_yang.algorithmRecord.backTrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

// leetcode 17 电话号码的字母组合
public class LetterCombination {
    /*
    定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
    2 -> abc    3 -> def
    4 -> ghi    5 -> jkl   6 -> mno
    7 -> pqrs   8 -> tuv   9 -> wxyz
     */
    // 记录 【数字 - 字母】 对应关系
    HashMap<Character, String> numberMap = new HashMap<Character, String>() {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };

    // 回溯法
    public List<String> letterCombinations(String digits) {
        // 避免题解中的特殊情况
        if ("".equals(digits))
            return new ArrayList<>();

        // 保存结果
        ArrayList<String> result = new ArrayList<>();
        // 保存可行解
        StringBuilder combination = new StringBuilder();

        backTrack(digits, result, combination, 0);
        return result;
    }

    private void backTrack(String digits, ArrayList<String> result, StringBuilder combination, int i) {
        int len = digits.length();
        if (i >= len) {
            result.add(combination.toString());
        } else {
            // 没搜索完，处理当前的数字
            char digit = digits.charAt(i);
            String letters = numberMap.get(digit);
            // 遍历所有可能
            for (int j = 0; j < letters.length(); j++) {
                // 添加字母到可行解中
                combination.append(letters.charAt(j));
                // 回溯
                backTrack(digits, result, combination, i + 1);
                // 恢复状态
                combination.deleteCharAt(i);
            }
        }
    }

    public static void main(String[] args) {
        LetterCombination solution = new LetterCombination();
        Print(solution.letterCombinations("23"));
        solution.letterCombinations("");
        solution.letterCombinations("2");
    }

    public static void Print(List<String> res) {
        for (String r : res) {
            System.out.print(r + " ");
        }
    }
}
